package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/11 14:17
 *
 数组中的逆序对:归并排序思想
 */

public class Main22 {

    int tmp[];
    int ans=0;
    public void merge(int []a,int l,int r){
        if(l>=r)return;
        int mid=(l+r)>>1;
        merge(a,l,mid);
        merge(a,mid+1,r);

        int i=l,j=mid+1,cnt=0;
        while(i<=mid&&j<=r){
            if(a[i]<=a[j]){
                //每放入一个i，那么就与之前已放入的j组成逆序对
                ans=(ans%1000000007)+j-mid-1;
                tmp[cnt++]=a[i++];
            }else{
                tmp[cnt++]=a[j++];
            }
        }
        while(i<=mid){
            ans=(ans%1000000007)+r-mid;//j-mid-1,同上
            tmp[cnt++]=a[i++];
        }
        while(j<=r){
            tmp[cnt++]=a[j++];
        }
        for(int k=0;k<cnt;++k){
            a[k+l]=tmp[k];
        }
    }

    public int InversePairs(int [] array) {
        if(array==null||array.length<2)return 0;
        this.tmp=new int[array.length];
        merge(array,0,array.length-1);
        for(int k=0;k<array.length;++k){
            System.out.print(array[k]+"");
        }
        System.out.println();
        return ans;
    }


    public static void main(String[] args) {
        int arr[]={1,2,3,4,5,6,7,0};
        System.out.println(new Main22().InversePairs(arr));
    }
}
